#include "sort.h"

void YuShen::AdjustDown(int* arr, int len, int parent)
{
  int child = parent * 2 + 1;
  while (child < len)
  {
    if (child + 1 < len && arr[child] < arr[child + 1]) ++child;
    if (arr[parent] < arr[child])
    {
      std::swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else break;
  }
}

void YuShen::HeapSort(int* arr, int len)
{
  assert(arr);
// 向下调整
  for (int i = (len - 2) / 2; i >= 0; --i) AdjustDown(arr, len, i);
  for (int i = 0; i < len; i++)
  {
    std::swap(arr[0], arr[len-1-i]);
    AdjustDown(arr, len-1-i, 0);
  }
}

void YuShen::_MergeSort(int* arr, int* tmp, int begin, int end)
{
  if (begin >= end) return;

  int left = begin;
  int middle = (end - begin) / 2 + begin;
  int right = middle + 1;

  _MergeSort(arr, tmp, left, middle);
  _MergeSort(arr, tmp, right, end);
  
  int i = begin;
  while (left <= middle && right <= end)
  {
    if (arr[left] < arr[right]) tmp[i++] = arr[left++];
    else tmp[i++] = arr[right++];
  }
  while (left <= middle) tmp[i++] = arr[left++];
  while (right <= end) tmp[i++] = arr[right++];
  memcpy(arr, tmp, sizeof(int) * (end - begin + 1));
}

void YuShen::MergeSort(int* arr, int len)
{
  assert(arr);
  int* tmp = new int[len];
  _MergeSort(arr, tmp, 0, len - 1);
}

void YuShen::MergeSortNoRecursive(int* arr, int len)
{
  assert(arr);
  int tmp[len];

  int gap = 1;
  while (gap < len)
  {
    for (int i = 0; i < len; i += gap * 2)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + gap*2 - 1;

      if (end1 >= len || begin2 >= len) break;
      if (end2 >= len) end2 = len - 1;

      int j = begin1;
      int n = end2 - begin1 + 1;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (arr[begin1] < arr[begin2]) tmp[j++] = arr[begin1++];
        else tmp[j++] = arr[begin2++];
      }
      while (begin1 <= end1) tmp[j++] = arr[begin1++];
      while (begin2 <= end2) tmp[j++] = arr[begin2++];
      memcpy(arr + i, tmp + i, sizeof(int) * n);
    }
    gap *= 2;
  }
}

int YuShen::_quickSort1(int* arr, int begin, int end)
{
  // 原始版本
  int left = begin + 1;
  int right = end;
  while (left < right)
  {
    while (left < right && arr[begin] <= arr[right]) right--;
    while (left < right && arr[left] <= arr[begin]) left++;
    if (left < right) std::swap(arr[left], arr[right]);
  }
  if (arr[begin] > arr[right]) std::swap(arr[begin], arr[right]);
  return right;
}
int YuShen::_quickSort2(int* arr, int begin, int end)
{
  // 挖坑版本
  int keyi = begin;
  int key = arr[begin];
  int left = begin + 1, right = end;
  while (left < right)
  {
    while (left < right && key <= arr[right]) right--;
    if (key > arr[right])
    {
      arr[keyi] = arr[right];
      keyi = right;
    }
    else break; 
    while (left < right && arr[left] <= key) left++;
    arr[keyi] = arr[left];
    keyi = left;
  }
  arr[keyi] = key;
  return keyi;
}

int YuShen::_quickSort3(int* arr, int begin, int end)
{
  // 双指针版本
  int left = begin;
  int right = begin + 1;
  while (right <= end)
  {
    if (arr[right] < arr[begin] && ++left != right) std::swap(arr[right], arr[left]);
    right++;
  }
  std::swap(arr[begin],arr[left]);
  return left;
}

void YuShen::_quickSort(int* arr, int begin, int end)
{
  if (begin >= end) return;
  int trage = _quickSort3(arr, begin, end); 
  _quickSort(arr, begin, trage - 1);
  _quickSort(arr, trage + 1, end);
}
void YuShen::QuickSort(int* arr, int len)
{
  assert(arr);

  _quickSort(arr, 0, len - 1);
}